package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//递归寻找:12ms 45% 7.4MB 95%
//先判断root,然后左右子树分别递归寻找q,p,找到了返回对应节点，左右都找到了，说明最近父结点是root
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == p.Val || root.Val == q.Val {
		return root
	}
	left := lowestCommonAncestor(root.Left, q, p)
	right := lowestCommonAncestor(root.Right, q, p)

	if left != nil && right != nil {
		return root
	}
	if left == nil {
		return right
	}
	return left
}

//还可以存储父节点，先序遍历将节点的父节点存储下来，然后q或者p节点根据存储的父节点，不断遍历到root，另一个节点再开始遍历，遇到visited直接返回，即最近的公共父节点
//parent := map[int]*TreeNode{} -- [子节点Val]*父节点;  visited := map[int]bool{} -- [已遍历节点]true
func lowestCommonAncestor1(root, p, q *TreeNode) *TreeNode {
	parent := map[int]*TreeNode{}
	visited := map[int]bool{}

	var dfs func(*TreeNode)
	//先序遍历,存储父节点
	dfs = func(r *TreeNode) {
		if r == nil {
			return
		}
		if r.Left != nil {
			//存储子节点值和父节点
			parent[r.Left.Val] = r
			dfs(r.Left)
		}
		if r.Right != nil {
			parent[r.Right.Val] = r
			dfs(r.Right)
		}
	}
	dfs(root)

	//遍历一个节点到root，并记录路线节点为visited
	for p != nil {
		visited[p.Val] = true
		p = parent[p.Val]
	}
	for q != nil {
		if visited[q.Val] {
			return q
		}
		q = parent[q.Val]
	}
	return nil
}

func main() {
	fmt.Println(lowestCommonAncestor(&TreeNode{
		2,
		&TreeNode{1, nil, nil},
		&TreeNode{3, nil, nil},
	},
		&TreeNode{2, nil, nil},
		&TreeNode{3, nil, nil}))

	fmt.Println(lowestCommonAncestor1(&TreeNode{
		2,
		&TreeNode{1, nil, nil},
		&TreeNode{3, nil, nil},
	},
		&TreeNode{2, nil, nil},
		&TreeNode{3, nil, nil}))
}
